package main

import "fmt"

func QuickSort(arr, arrAddr []int) []int {
	length := len(arr)

	if length <= 1 {
		return arrAddr //一个元素的数组，直接返回
	} else {
		splitaddr := arrAddr[0]              // 第一个地址下标
		lowaddr := make([]int, 0, 0)         //存储比我小的
		highaddr := make([]int, 0, 0)        //存储比我大的
		midaddr := make([]int, 0, 0)         //存储与我相等
		midaddr = append(midaddr, splitaddr) //加入第一个相等

		split := arr[0]           //以第一个为基准
		low := make([]int, 0, 0)  //存储比我小的
		high := make([]int, 0, 0) //存储比我大的
		mid := make([]int, 0, 0)  //存储与我相等
		mid = append(mid, split)  //加入第一个相等

		for i := 1; i < length; i++ {
			if arr[i] > split {
				highaddr = append(highaddr, arrAddr[i])
				high = append(high, arr[i])
			} else if arr[i] < split {
				lowaddr = append(lowaddr, arrAddr[i])
				low = append(low, arr[i])
			} else {
				midaddr = append(midaddr, arrAddr[i])
				mid = append(mid, arr[i])
			}
		}

		lowaddr, highaddr = QuickSort(low, lowaddr), QuickSort(high, highaddr)

		myAddr := append(append(lowaddr, midaddr...), highaddr...)

		return myAddr

	}

}

func main() {
	arr := []int{1, 9, 2, 8, 3, 7, 6, 4, 5, 10}
	arraddr := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	fmt.Println(arr)
	fmt.Println(arraddr)
	fmt.Println("-------------")
	myarr := QuickSort(arr, arraddr)
	fmt.Println(arr)
	fmt.Println(myarr)
	fmt.Println("-------------")

	for _, v := range myarr {
		fmt.Println(arr[v])
	}

}
